import java.util.PriorityQueue;

/**
 * @author hewei
 * @version 1.0
 * @description: 767. 重构字符串
 * @date 2022/8/22 16:55
 */

public class ReorganizeString {

    public static void main(String[] args) {
        ReorganizeString reorganizeString = new ReorganizeString();
        System.out.println(reorganizeString.reorganizeString("aaaabbbcc"));
    }

    public String reorganizeString(String s) {
        char[] chars = s.toCharArray();
        int[] temp = new int[26];
        for (char aChar : chars) {
            temp[aChar - 'a']++;
        }
        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> temp[b] - temp[a]);
        for (int i = 0; i < 26; i++) {
            if (temp[i] != 0) heap.offer(i);
        }
        char[] ans = new char[s.length()];
        int index = 0;
        while (heap.size() >= 2) {
            Integer poll = heap.poll();
            Integer poll1 = heap.poll();
            temp[poll]--;
            temp[poll1]--;
            ans[index++] = (char) (poll + 'a');
            ans[index++] = (char) (poll1 + 'a');
            if (temp[poll] != 0) heap.offer(poll);
            if (temp[poll1] != 0) heap.offer(poll1);
        }
        if (heap.size() == 1 && temp[heap.peek()] > 1) return "";
        if (heap.size() == 1) ans[ans.length - 1] = (char) (heap.poll() + 'a');
        return new String(ans);
    }
}
